package club.xiaojiawei.binarytree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/18/22 9:18 PM
 * @question 236. 二叉树的最近公共祖先
 * @description 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
public class LowestCommonAncestor236 {

    public static void main(String[] args) {
        LowestCommonAncestor236 test = new LowestCommonAncestor236();
        TreeNode treeNode = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(4);
        TreeNode root = new TreeNode(3,
                new TreeNode(5,
                        new TreeNode(6),
                        new TreeNode(2,
                                new TreeNode(7),
                                treeNode1)),
                new TreeNode(1,
                        new TreeNode(0),
                        new TreeNode(8)));
        TreeNode result = test.lowestCommonAncestor(root, treeNode, treeNode1);
        System.out.println(result);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        recursion(root, p, q,"1");
        return result;
    }

    TreeNode result = null;
    String binary1 = "", binary2 = "";

    String binary = "";

    /**
     * 递归+二进制
     * @param node
     * @param p
     * @param q
     * @param binary
     */
    public void recursion(TreeNode node, TreeNode p, TreeNode q, String binary){
        if (node == null || (!binary1.equals("") && !binary2.equals(""))){
            return;
        }
        if (p == node){
            binary1 = binary;
            if (!binary2.equals("")){
                String temp;
                if (binary1.length() > binary2.length()){
                    temp = binary1;
                    binary1 = binary2;
                    binary2 = temp;
                }
                for (int i = binary1.length(); i > 0; i--){
                    if (binary2.indexOf(binary1.substring(0, i)) == 0){
                        this.binary = binary1.substring(0, i);
                        break;
                    }
                }
            }
        }else if (q == node){
            binary2 = binary;
            if (!binary1.equals("")){
                String temp;
                if (binary1.length() > binary2.length()){
                    temp = binary1;
                    binary1 = binary2;
                    binary2 = temp;
                }
                for (int i = binary1.length(); i > 0; i--){
                    if (binary2.indexOf(binary1.substring(0, i)) == 0){
                        this.binary = binary1.substring(0, i);
                        break;
                    }
                }
            }
        }
        recursion(node.left, p, q, binary + "0");
        recursion(node.right, p , q, binary + "1");
        if (this.binary.equals(binary)){
            result = node;
        }
    }

    private TreeNode ans = null;

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lSon = dfs(root.left, p, q);
        boolean rSon = dfs(root.right, p, q);
        if ((lSon && rSon) || ((root.val == p.val || root.val == q.val) && (lSon || rSon))) {
            ans = root;
        }
        return lSon || rSon || (root.val == p.val || root.val == q.val);
    }

    /**
     * 官方-递归
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }

    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs2(TreeNode root, TreeNode p, TreeNode q) {
        if (parent.get(p.val) != null && parent.get(q.val) != null){
            return;
        }
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs2(root.left, p, q);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs2(root.right, p, q);
        }
    }

    /**
     * 官方-存储父节点
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        dfs2(root, p, q);
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }


    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
